Error regions in quantum state tomography: computational complexity caused by geometry of quantum states

摘要

The outcomes of quantum mechanical experiments are inherently random. It istherefore necessary to develop stringent methods for quantifying the degree ofstatistical uncertainty about the results of quantum experiments. For theparticularly relevant task of quantum state estimation, it has been shown thata significant reduction in uncertainty can be achieved by taking the positivityof quantum states into account. However -- the large number of partial resultsand heuristics notwithstanding -- no efficient general algorithm is known thatproduces an optimal uncertainty region from experimental data and the priorconstraint of positivity. Here, we make this problem precise and show that thegeneral case is NP-hard. Our result leaves room for the existence of efficientapproximate solutions, and therefore does not yet imply that the practical taskof quantum uncertainty quantification is intractable. However, it does showthat there exists a non-trivial trade-off between optimality and computationalefficiency for error regions. We prove two versions of the result: One forfrequentist and one for Bayesian statistics.